The present application relates to a system and method for packet classification. More specifically, the present application relates to a system and method implementing packet classification using a continuously updated cache of evolving rules.
Data packets received at a router input port are classified to determine an action to be performed on the packet. The action may include forwarding the packet, routing the packet to a particular application, providing expedited delivery of the packet, discarding the packet, etc. Packet classification is needed for services that require the capability to distinguish and isolate traffic (i.e., packets) in different flows for suitable processing. Exemplary services include packet filter, for example denying all packets from a known source, policy routing, for example routing all voice over IP traffic over a separate ATM network, traffic rate limiting, for example ensuring that any one source does not overload the network, etc. To implement the services, a packet classifier implements a series of rules that determine the action(s) to be taken for a packet based on header fields included in the packet.
A packet classifier matches several fields in the packet header of an incoming packet against a set of predefined rules. Exemplary fields include possible values of source and destination addresses, protocol fields, port numbers, etc. If all of the header fields associated with the packet match the corresponding ranges of a rule, the packet is considered to obey the rule and the action associated with the rule will be performed for that packet. For a specific packet, more than one rule can match the packet.
Accordingly, rules may be ranked by priority, such that the action associated with the highest rank rule will be performed for the packet.
Packet classification across multiple header fields may be a processor intensive operation. Packet classification algorithms are inherently limited by the tradeoff between memory usage and classification speed. A hardware based classification, such as Ternary Content Addressable Memory (TCAM), where the rule matching speed is considerably faster, has traditionally been used to the perform classification because of this limitation. However, hardware based classification is more expensive and consumes both more physical space and more power compared to packet classification algorithms. This is a significant disadvantage for mobile computing devices.
A “smart rule cache” that combines simple hardware and software has been used to provide a balance between the speed of hardware and the low expense of software. The hardware consists of a small on-chip cache, large enough to store one or more evolving rules, along with some simple logic to match incoming packets against the stored rules. The software component consists of algorithms by which the rules in the cache continuously evolve in response to changes in incoming traffic pattern.
Smart rule caches utilizes evolving rules that are semantically consistent with an original rule set meaning that packets classified using the evolving rules will be classified the same as they would under the original rule set. Smart rule caches generally include a small set of evolving rules. To maintain the small number of rules, a single evolving rule can overlap several rules of the original rule set, so long as the evolving rules remain semantically consistent. Evolving rules must be continually verified over the entire original rule set to ensure that they remain semantically consistent. One limitation for smart rules cache performance is the time required to re-compute the cached rules.
What is needed is a system and method for providing efficient packet classification that reduces the costs associated with evolving the cached rule set using an efficient smart rule caching system and method.